package com.moyoutian.leetcode;

import java.util.*;

/**
 * 846. 一手顺子
 * <p>
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 * <p>
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
 * <p>
 * 输出：true
 * <p>
 * 解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：hand = [1,2,3,4,5], groupSize = 4
 * <p>
 * 输出：false
 * <p>
 * 解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= hand.length <= 104
 * <p>
 * 0 <= hand[i] <= 109
 * <p>
 * 1 <= groupSize <= hand.length
 * <p>
 * <p>
 * 注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
 */
public class Demo846 {
    public static void main(String[] args) {
        int[] hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
        int groupSize = 3;
        System.out.println(isNStraightHand(hand, groupSize));
    }


    public static boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        //保证顺序
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //保证重复,和计数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < hand.length; i++) {
            Integer c = map.get(hand[i]);
            if (c == null) {
                map.put(hand[i], 1);
                priorityQueue.add(hand[i]);
            } else {
                map.put(hand[i], c + 1);
            }
        }
        while (!priorityQueue.isEmpty()) {
            Integer cn = priorityQueue.peek();
            for (int i = 0; i < groupSize; i++) {
                int new_cn = cn + i;
                Integer cc = map.get(new_cn);
                if (cc == null) {
                    return false;
                } else if (cc == 1) {
                    map.remove(new_cn);
                    priorityQueue.poll();
                } else {
                    map.put(new_cn, cc - 1);
                }
            }
        }
        return true;
    }

    public static boolean isNStraightHand1(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        // key:数字号 val:数量
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int value : hand) {
            treeMap.put(value, treeMap.getOrDefault(value, 0) + 1);
        }
        Map.Entry<Integer, Integer> entry = treeMap.firstEntry();
        while (entry != null) {
            int i = entry.getKey();
            //从最小key开始，到i+groupSize结束
            int end = i + groupSize;
            for (; i < end; i++) {
                Integer temp = treeMap.get(i);
                if (temp == null) {
                    return false;
                }
                if (temp - 1 == 0) {
                    treeMap.remove(i);
                } else {
                    treeMap.put(i, temp - 1);
                }
            }
            entry = treeMap.firstEntry();
        }
        return true;
    }


}
